Обилазак (претрага) у дубину и ширину
Основни задаци над графом се често своде на то да се кренувши од неког почетног чвора и праћењем грана обиђу сви чворови графа који су достижни из тог полазног чвора. Ако је неусмерен граф повезан тиме ће се обићи сви његови чворови, а ако није, онда ће се обићи компонента повезаности којо припада почетни чвор. Код усмерених графова на овај начин ће се обићи компонента јаке повезаности којој припада почетни чвор.
Постоје два основна алгоритма за обилазак графа: претрага у дубину и претрага у ширину.
Оба се могу представити следећом општом схемом.
dodaj pocetni cvor u kolekciju K dok kolekcija K nije prazna: uzmi cvor c iz kolekcije K ako c nije oznacen: oznaci c za svaku granu cc' ubaci c' u kolekciju K
Означавањем чворова постижемо то да се алгоритам не упада у бесконачну петљу. Ако је колекција K стек, тада се ради о претрази у дубину, ако је колекција K ред, ради се о претрази у ширину, а ако је у питању ред са приоритетом, ради се о претрази са приоритетом (њу у наставку нећемо детаљно описивати).
Претрага у дубину се често имплементира и рекурзивно.
dfs(cvor c): ako c nije oznacen: oznaci c ulazna_obrada_cvora(c) za svaku granu cc' dfs(c') izlazna_obrada_cvora(c)
У неким алгоритмима обраду чвора вршимо први пут када на њега наиђемо (тј. је тзв. улазна обрада), док у неким алгоритмима обраду вршимо тек на крају, када обрадимо све потомке чвора.
Претрага у дубину подразумева да се дуж неку путању спуштамо докле год можемо и тек када не можемо да нађемо више непосећених чворова, онда се враћамо назад и разматрамо друге гране из претходно посећених чворова. Претрага у ширину подразумева да се граф обилази по нивоима. Прво се обилази полазни чвор, затим они чворови до којих се из полазног може стићи само путем једне гране, затим они чворови до којих се из полазног може стићи само путем две гране и тако даље.